1. Field of the Invention
The present invention is related to image processing, and more specifically to construction of an image from multiple sub-images, for example as may be used to compute a 2-dimensional output image from real-time sample pixel data.
2. Description of the Prior Art
In many applications it is necessary to “construct” (or “reconstruct”) an image from a number of sub-images. One common example of a device employing image reconstruction is a flat bed document scanner. A document placed on a platen is scanned by a moving image capture device. Multiple strips of the document (e.g., as measured perpendicular to the document's length), between one and several pixels in height, are captured by the image capture device as it progresses along the length of the document. The relative motion between the image capture device and the document (or other item being imaged) is referred to herein as a scan, and the speed of this relative motion is referred to herein as the scan rate. Each strip is a portion of the document image referred to as a sub-image. The multiple sub-images may be “stitched” together by software to construct a 2-dimensional image of the entire document (or alternatively, the raw data may be otherwise processed).
One critical aspect of flat bed scanners is that the scan rate (relative rate of motion between scanner device and item to be scanned, regardless of which is moving) is known and/or controllable. From this, it is possible to accurately piece together the various sub-images. However, if the rate of scan is not known, or is constantly changing over time, construction of the image from the various sub-images is problematic.
There are many devices today in which the scan rate is not known or varies over time. For example, a typical strip-sensor fingerprint image capture device of the type used for biometric identification is several pixels in the scan direction, by several hundred pixels in a second, orthogonal dimension, referred to herein as the width direction. Commonly, a user slides a finger over a sensor strip in the scan direction (although the sensor may move relative to the finger in some examples). As the finger is slid over the sensor strip, images of the fingerprint are periodically captured. Multiple sub-images are thus obtained. The sub-images are subsequently mathematically assembled (or stitched) together to form a “computed” image of the fingerprint. This image can be compared with a reference image to allow or deny access to a computer, a building, etc.
However, such a device and related methods present several challenges. First, unlike the motion of the image capture device in the flat bed scanner, there is generally no synchronized control over the scan rate—the user is in complete control over the rate at which the finger is moved over the sensor. Second, unlike the document in the flat bed scanner, the user's finger moves with several degrees of freedom relative to the sensor, for example the width direction and the scan direction. Thus, a critical step in constructing an image based on data from a strip sensor fingerprint scanner, and indeed any application in which the scan rate and/or direction (in one or both dimensions) vary or are unknown, is properly ordering and positioning the sub-images so as to assemble an accurate image. (While in some image capture systems image rotation is also a degree of freedom, image rotation is beyond the scope of this disclosure.)
Efforts have been made to address the issue of relative scan rate by mechanically or mathematically determining the rate of relative motion between the sensor device and the finger (as an example of an object being scanned). However, each present problems: variations in scan rate are difficult to accommodate, mechanical systems are subject to reliability and wear issues, both mechanical and mathematical systems indiscriminately assemble sub-images together based on time and are generally low precision, mathematical systems require significant system memory and processing, etc.
One method employed to properly piece together an image from a sequence of partially overlapping sub-images which does not depend upon a knowledge of the scan rate is to determine the correlation between various sub-images (the sub-images, when stored, are also referred to as frames). In image processing, the calculated correlation between a first frame F1 and a second frame F2 is defined as:
                    Correlation        =                                            (                              ∑                                                      a                    i                                    ⁢                                      b                    i                                                              )                        2                                ∑                                          a                i                2                            ⁢                              ∑                                  b                  i                  2                                                                                        (        1        )                            where ai is the image data of frame F1                     bi is the image data of frame F2 The image data referred to in equation (1) typically relates to the pixel's gray scale value, intensity, luminance, color, etc.                        
Alternatives to Correlation (sometimes mistakenly referred to as correlation) are the Sum of Absolute Differences, defined as Σabs(ai−bi) and the Sum of Squared Differences, defined as Σ(ai−bi)2.
In one example of the correlation technique, all possible cases of overlap of two successive partial images are examined for a correlation in the overlapping pixels. For example, U.S. Pat. No. 6,289,114, which is incorporated herein, teaches the capture of images of a fingerprint by a one-dimensional sensor array. Trials are performed in which all possible overlapping cases of two successive images are examined for correlation between pixels in the overlapping region of the two images. The two images are stitched together in relative position as between the two which produced the “best” correlation. A distinct disadvantage of this approach is that the number of calculations required in order to examine all possible cases of overlap is tremendous, meaning the processing is slow and labor intensive and the demands on system resources (memory, processor cycles) are high.
One known method to address the quantity of calculations required for a correlation solution is to examine only selected portions of two images in their possible overlapping states. We will assume that two frames, each representing a different portion of an image have an overlapping rectangular region. Using the method of correlation, portions of the frames, called windows, can be used to calculate how and where the two frames fit together as part of the larger image. The first window is a specific M pixel by N pixel (M×N) portion of the first frame referred to as a “master” or “reference” window. The second window is a selected M×N portion of the second frame referred to as the “slave”. For each possible M×N slave window on the second frame, correlation between that M×N slave window and the reference M×N window is calculated. This produces a number of window pairs (reference and slave), each pair having a calculated correlation (that is, a measure of how “alike” the two windows are). That pair of windows with the highest correlation are considered to be fully overlapping. From a knowledge of the positions of the reference and slave windows, the image displacement between the two partially overlapping frames (the shift in the image from one frame to the next) is determined. FIG. 9 is an example of first and second frames 10, 12, with reference window 14 and a plurality of slave windows 16a, 16b, 16c (not all slave windows are illustrated). Windows 14 and 16b are found to have the highest correlation. It is then determined that the position shift between the capture of the first frame 10 and the second frame 12 is two pixels in the scan direction and zero pixels in the width direction. From this, frames 10 and 12 may be stitched together to form the reconstructed image 18 shown in FIG. 10.
As correlation provides a simple comparison between two windows, displacement estimation algorithms based on correlation operate by searching window pairs. As each pair is evaluated, the correlation is recorded. The pair with the highest correlation can then be used to represent the starting point and ending point for displacement estimation, and the position at which the second frame is properly stitched to the first frame can then be determined.
However, it will be appreciated that correlation methods have certain drawbacks. First, the process involves selecting a reference frame and analyzing a great number of slave frames. That is, even in light of the windowing technique described above, a great number of comparisons must be made before a system can be certain it has located the highest correlation. Intelligent search techniques can be used to reduce the size of the search set, but still the number of computations is quite large. Second, by construction, correlation based methods must operate on data with reference to a grid, typically where a point on the grid represents one pixel. This leads to artifacts, dropped features, and other registration problems, especially when capturing and reconstructing non-linear patterns such as fingerprint patterns. Third, the maximum achievable precision of correlation methods is directly related to the resolution of the input image. For an image of given input resolution (e.g., 500 dpi) the maximum precision obtainable is +/−1.0 pixels in the x- and y-directions. Preprocessing by discrete interpolation can be used to increase the resolution for the correlation algorithm, the post processing the stitched image to de-interpolate back to the initial image resolution. But this greatly increases the computational and memory requirements.
Accordingly, an improved method for image construction from sequential sub-images is needed in the art. The method should be computationally light weight, allow for non-linear image features, and be of improved precision (preferably independent of the image resolution).